Clique and Constraint Models for Maximum Common (Connected) Subgraph Problems

摘要

The maximum common subgraph problem is to find the\udlargest subgraph common to two given graphs. This problem can be\udsolved either by constraint-based search, or by reduction to the maximum\udclique problem. We evaluate these two models using modern algorithms,\udand see that the best choice depends mainly upon whether the graphs\udhave labelled edges. We also study a variant of this problem where the\udsubgraph is required to be connected. We introduce a filtering algorithm\udfor this property and show that it may be combined with a restricted\udbranching technique for the constraint-based approach. We show how to\udimplement a similar branching technique in clique-inspired algorithms.\udFinally, we experimentally compare approaches for the connected version,\udand see again that the best choice depends on whether graphs have labels